class Solution {
public:
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
    	this->rows = rows;
    	this->cols = cols;
    	this->size = rows*cols;
    	this->flag = false;
		for(int i = 0 ; i < size; ++i)
			if(matrix[i] == str[0])
				moveCore(matrix,str,i);
    	return flag;
    }

    void moveCore(char *matrix,char *str,int start)
    {
    	int path[size];
    	for(int i = 0 ; i < size; ++i)
			path[i] = 0;
    	path[start] = 1;
    	moveNext(matrix,str+1,path,start);
    }
    void moveNext(char *matrix,char *str,int *path,int last)
    {
    	if(!*str)
    		flag = true;
    	//右移
    	if(last + 1 < size && !path[last+1] && *str == matrix[last+1])
    	{
    		path[last+1] = 1;
    		moveNext(matrix,str+1,path,last+1);
    		path[last+1] = 0;
    	}
    	//左移
    	if(last -1 > -1 && !path[last-1] && *str == matrix[last -1])
    	{
    		path[last-1] = 1;
    		moveNext(matrix,str+1,path,last-1);
    		path[last-1] = 0;
    	}
    	//上移
    	if(last - cols > -1 && !path[last-cols] && *str == matrix[last-cols])
    	{
    		path[last-cols] = 1;
    		moveNext(matrix,str+1,path,last-cols);
    		path[last-cols] = 0;
    	}
    	//下移
    	if(last + cols < size && !path[last + cols] && *str == matrix[last+cols])
    	{
    		path[last+cols] = 1;
    		moveNext(matrix,str+1,path,last+cols);
    		path[last+cols] = 0;
    	}
    }
private:
	bool flag;
	int rows;
	int cols;
	int size;

};